// 版权归Go作者所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 通过诱导排序（SAIS）构造后缀数组。
// 参见葛农、张森和陈伟红，
// “线性时间后缀数组构造的两种有效算法”，
// 特别是第3节(https:
// 另见http:
// 
// 受Yuta Mori的sais lite启发进行了优化
// (https:
// 
// 以及其他新的优化。

// 这些函数中的许多都是由
// 它们操作的类型的大小参数化的。generator gen.go制作
// 这些函数的副本，用于其他尺寸。
// 具体来说是：
// 
// -一个名称以_8_32结尾的函数采用[]字节和[]int32参数
// 并复制到_32_32、_8_64和_64_64形式。
// 后缀32_32和64_64被缩短为普通的32和64。
// 在创建_32_32和_64_64表单时，函数体中包含文本“仅字节”或“256”的任何行都会被删除。
// （这些行通常是8位特定优化。）
// 
// -名称以_32结尾的函数在[]int32 
// 上运行，并复制为_64形式。（请注意，它可能仍然需要[]字节，
// 但不需要将[]字节
// 扩展为完整整数数组的函数版本。）

// 这段代码的整体运行时间在输入大小上是线性的：
// 它运行一系列线性过程，将问题简化为
// 一个子问题，最多是一半大，递归调用自己，
// 然后运行一系列线性过程，将子问题的答案
// 转换为原始问题的答案。
// 这给出了T（N）=O（N）+T（N/2）=O（N）+O（N/2）+O（N/4）+O（N）。
// 
// 代码的大纲，包括正向和反向扫描
// 到O（N）大小的数组，is:
// 
// sais_I_N 
// placeLMS_I_B 
// bucketMax_I_B 
// freq I_B 
// /<scan+freq>（2）
// （4）
// /<scan+freq>（5）
// /<scan+sa，随机文本，random bucket>.（6）
// （7）
// /<scan+freq>（8）
// /<scan-sa，random text，random bucket>.（9）
// map\U B 
// <扫描-sa>（11）
// recurse\U B 
// （对于大小不超过1/2输入的子问题，递归调用sais\U B\U B，通常更小）
// unmap I\U B 
// <扫描-文本>（12）
// <扫描+sa>（13）
// 展开\u I\u B 
// bucketMax\u I\u B
// frequer_I_B 
// <scan+text，经常被优化掉>（14）
// <scan+freq>（15）
// <scan-sa，random text，random bucket>（16）
// bucketMin_I_B 
// /<scan+freq>（18）
// /<scan+sa，随机文本，随机bucket>（19）
// 诱导_I_B 
// bucketMax_I_B 
// /<freq_I_B 
// 
// 这里，_B表示后缀数组大小（_32或_64）和_I输入大小（_8或_B）。
// 
// 大纲显示，对于给定的递归级别，通常有22个扫描通过
// O（N）大小的数组。
// 在顶层，操作8位输入文本，
// 六个频率扫描的大小是固定的（256），而不是潜在的
// 输入大小。此外，频率计算一次并缓存
// 只要有空间，就可以这样做（一般来说，几乎总是有空间，
// 并且总是在顶层有空间），这就消除了除
// 之外的所有文本扫描（即6个文本扫描中的5个）。
// 因此递归的顶层只进行22-6-5=11 
// 输入大小的扫描，而一个典型的级别进行16次扫描。
// 
// 线性扫描的成本远不及
// 在几次
// 扫描期间对文本的随机访问（特别是上面标记的#6、#9、#16、#19、#22）。
// 在真实文本中，由于文本
// （与Burrows Wheeler压缩非常有效的原因相同）的重复结构，访问除了局部性之外没有太多。
// 对于随机输入，没有局部性，这使得那些
// 访问更加昂贵，尤其是当文本
// 不再适合缓存时。例如，在50MB的Go源代码上运行时，InquiredSubl_8_32 
// （在递归的顶层只运行一次）
// 需要0.44s，而在50MB的随机输入上，需要2.55s。
// 几乎所有的相对减速都是通过文本访问来解释的：
// 
// c0，c1:=text[k-1]，text[k]
// 
// 该行在移动文本上运行0.23秒，在随机文本上运行2.02秒。

// go:generate go run gen.go 

package suffixarray

// text_32返回输入文本的后缀数组。
// 它要求len（文本）与int32 
// 相匹配，并且调用者将sa归零。
func text_32(text []byte, sa []int32) {
	if int(int32(len(text))) != len(text) || len(text) != len(sa) {
		panic("suffixarray: misuse of text_32")
	}
	sais_8_32(text, 256, sa, make([]int32, 2*256))
}

// sais_8_32计算文本的后缀数组。
// 文本必须只包含[0，textMax]中的值。
// 后缀数组存储在sa中，调用者
// 必须确保已将其归零。
// 调用者还必须提供临时空间tmp 
// 和len（tmp）≥ textMax。如果len（tmp）≥ 2*textMax 
// 然后算法运行得更快一些。
// 如果sais_8_32修改tmp，它会在返回时设置tmp[0]=-1。
func sais_8_32(text []byte, textMax int, sa, tmp []int32) {
	if len(sa) != len(text) || len(tmp) < int(textMax) {
		panic("suffixarray: misuse of sais_8_32")
	}

	// 琐碎的基本情况。排序0或1件事情很容易。
	if len(text) == 0 {
		return
	}
	if len(text) == 1 {
		sa[0] = 0
		return
	}

	// 建立由文本字符索引的切片
	// 保留字符频率和桶排序偏移量。
	// 如果一个切片只有足够的tmp，
	// 我们将其设置为桶偏移量，并在每次需要时重新计算
	// 字符频率。
	var freq, bucket []int32
	if len(tmp) >= 2*textMax {
		freq, bucket = tmp[:textMax], tmp[textMax:2*textMax]
		freq[0] = -1 // 标记为未初始化
	} else {
		freq, bucket = nil, tmp[:textMax]
	}

	// SAIS算法。cun chu defg
	// 有关每个函数在算法中的角色，请参见文档中的各个函数。
	numLMS := placeLMS_8_32(text, sa, freq, bucket)
	if numLMS <= 1 {
		// 0或1项已排序。什么都不做。
	} else {
		induceSubL_8_32(text, sa, freq, bucket)
		induceSubS_8_32(text, sa, freq, bucket)
		length_8_32(text, sa, numLMS)
		maxID := assignID_8_32(text, sa, numLMS)
		if maxID < numLMS {
			map_32(sa, numLMS)
			recurse_32(sa, tmp, numLMS, maxID)
			unmap_8_32(text, sa, numLMS)
		} else {
			// 如果maxID==numLMS，则每个LMS子串
			// 是唯一的，因此两个LMS后缀
			// 的相对顺序仅由前面的LMS子串决定。也就是说，LMS后缀排序顺序与
			// （更简单的）LMS子字符串排序顺序匹配。
			// 将原始LMS子字符串顺序复制到
			// 后缀数组目标中。
			copy(sa, sa[len(sa)-numLMS:])
		}
		expand_8_32(text, freq, bucket, sa, numLMS)
	}
	induceL_8_32(text, sa, freq, bucket)
	induceS_8_32(text, sa, freq, bucket)

	// 为来电者标记我们过度编写了tmp。
	tmp[0] = -1
}

// freq_8_32返回文本的字符频率
// 作为按字符值索引的片段。
// 如果freq为零，则freq_8_32使用并返回bucket。
// 如果freq为非零，freq_8_32假定freq[0]>=0 
// 表示已经计算了频率。
// 如果频率数据被覆盖或未初始化，则
// 调用者必须设置freq[0]=-1，以便在下次需要时强制重新计算
// 频率数据。
func freq_8_32(text []byte, freq, bucket []int32) []int32 {
	if freq != nil && freq[0] >= 0 {
		return freq // 已计算
	}
	if freq == nil {
		freq = bucket
	}

	freq = freq[:256] // 消除频率[c]以下的边界检查
	for i := range freq {
		freq[i] = 0
	}
	for _, c := range text {
		freq[c]++
	}
	return freq
}

// bucketMin_8_32将桶中字符c的最小索引
// 存储在桶中，以桶排序文本。
func bucketMin_8_32(text []byte, freq, bucket []int32) {
	freq = freq_8_32(text, freq, bucket)
	freq = freq[:256]     // 建立len（freq）=256，所以0≤ i<256 
	bucket = bucket[:256] // 消除bucket的边界检查[i]
	total := int32(0)
	for i, n := range freq {
		bucket[i] = total
		total += n
	}
}

// bucketMax_8_32将bucket中的最大索引
// 存储在bucket中，用于bucket排序文本中的字符c。
// c的桶索引是[min，max]。
// 也就是说，max是该桶中最后一个索引的过去一个。
func bucketMax_8_32(text []byte, freq, bucket []int32) {
	freq = freq_8_32(text, freq, bucket)
	freq = freq[:256]     // 建立len（freq）=256，所以0≤ i<256低于
	bucket = bucket[:256] // 消除桶的边界检查[i]低于
	total := int32(0)
	for i, n := range freq {
		total += n
		bucket[i] = total
	}
}

// SAIS算法通过sa进行一系列扫描。
// 以下每个函数都实现一次扫描，
// 并且这些函数按照它们在算法中执行的顺序出现在这里。

// placeLMS_8_32将文本的LMS子字符串的最终字符
// 。
// 
// 文本末尾的假想哨兵字符
// 是最终LMS子字符串的最后一个字符，但没有用于假想哨兵字符
// 的存储桶，它的值小于任何实数字符。
// 因此，调用者必须假装sa[-1]==len（文本）。
// 
// LMS子字符串字符的文本索引总是≥ 1 
// （第一个LMS子字符串前面必须有一个或多个L型
// 字符，这些字符不属于任何LMS子字符串），
// 因此使用0作为“不存在”后缀数组条目是安全的，
// 在本函数和大多数后续函数中都是如此
// （直到下面的第8_32页）。ABCFDG＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊？
func placeLMS_8_32(text []byte, sa, freq, bucket []int32) int {
	bucketMax_8_32(text, freq, bucket)

	numLMS := 0
	lastB := int32(-1)

	// 也就是说，i+1是LMS子串的起始位置。
	// 这些可以被提升到一个带有回调的函数中，
	// 但是速度代价很大。相反，我们只是在这个源文件中写了几行。下面的副本
	// 指的是原版建立的模式，即
	// “LMS子字符串迭代器”。
	// 
	// 在文本的每次扫描中，c0、c1是文本的连续字符。
	// 在这个反向扫描中，c0==text[i]和c1==text[i+1]。
	// 通过向后扫描，我们可以根据通常的定义跟踪当前
	// 位置是S型还是L型：
	// 
	// /-位置len（text）是S型，带有文本[len（text）]=-1（哨兵）
	// /-位置i是S型，如果text[i]<text[i+1]，或者如果text[i]==text[i+1]&&i+1是S型。如果text[i]>text[i+1]，则位置i是L型。如果text[i]==text[i+1]&&i+1是L型。如果text[i]==text[i+1]&&i+1是S型。如果text[i]==c1，否则就别管它了。
	// 我们想用前面的L来标识所有的S位置。
	// 位置len（文本）就是这样定义的一个位置，但是我们有
	// 没有地方写它，所以我们通过在循环开始时不正确地设置isTypeS=false来消除它。
	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// Bucket索引i+1用于LMS子字符串的开始。
			b := bucket[c1] - 1
			bucket[c1] = b
			sa[b] = int32(i + 1)
			lastB = b
			numLMS++
		}
	}

	// 我们记录了LMS子串的开始，但确实想要结束。
	// 幸运的是，有两个不同之处，开始索引和结束索引是相同的。第一个区别是最右边的LMS子字符串的结束索引是len（text），因此调用方必须假装sa[-1]==len（text），如上所述。
	// 第二个区别是，第一个最左边的LMS子字符串开始索引
	// 不会结束一个较早的LMS子字符串，因此作为优化，我们可以省略最左边的LMS子字符串开始索引（我们编写的最后一个）。
	// 
	// 异常：如果numls<=1，调用方根本不需要处理
	// 递归，并且会将结果视为包含LMS子字符串。
	// 在这种情况下，我们不会删除最终条目。
	if numLMS > 1 {
		sa[lastB] = 0
	}
	return numLMS
}

// INDUCTSUBL_8_32将LMS子字符串
// 的L型文本索引插入sa，假设LMS子字符串
// 的最终字符已插入sa，按最终字符排序，并位于相应字符桶的
// 右（非左）端。
// 每个LMS子字符串的形式（作为regexp）/S+L+S/：
// 一个或多个S型、一个或多个L型、最终S型。
// INDUCTSUBL_8_32只留下最左边的L型文本
// 每个LMS子字符串的索引。也就是说，它删除条目上存在的最后一个S型
// 索引，然后插入但删除
// 内部也有L型索引。
// （只有最左边的L型指数才需要诱导子8_32。）
func induceSubL_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶左侧的位置。
	bucketMin_8_32(text, freq, bucket)
	bucket = bucket[:256] // 取消对

	// 下面的bucket[cB]的边界检查
	// 当我们从左到右扫描数组时，每个sa[i]=j>0都是一个正确的
	// 排序后缀数组条目（对于文本[j:]），我们知道j-1是L类型。
	// 因为j-1是L类型，现在将其插入sa将正确排序。
	// 但我们想区分类型为L和类型为S的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果在j-1前面加上类型S，我们通过对其求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i´>i在sa[i´发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递可以看到索引j、j-1、j-2、j-3、
	// 等等，它们是按排序但不一定是相邻的顺序排列的，直到它找到
	// 一个前面有一个S类型索引的索引，此时它必须停止。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 然后将sa[i]<0翻转为-sa[i]，这样循环结束时，sa包含
	// 每个LMS子串的最左边的L型索引的索引。
	// 
	// 因此，后缀数组sa同时充当输入、输出、
	// 和一个精心定制的工作队列。

	// placeLMS_8_32漏掉了隐式条目sa[-1]==len（text），
	// 对应于识别的L型索引len（text）-1。
	// 在sa从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket index:
	// 我们正在按排序顺序处理后缀
	// 并访问排序前由
	// 字节索引的bucket，这仍然是
	// 具有很好的局部性。
	// 不变量：b被缓存，可能是bucket[cB]的脏拷贝。
	cB := c1
	b := bucket[cB]
	sa[b] = int32(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		if j < 0 {
			// 为调用者保留已发现的type-S索引。
			sa[i] = int32(-j)
			continue
		}
		sa[i] = 0

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 所以我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，请将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则排队-k为调用者保存。
		k := j - 1
		c0, c1 := text[k-1], text[k]
		if c0 < c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int32(k)
		b++
	}
}

// INDUCTSUB_8_32将LMS子字符串的S型文本索引
// 插入sa，假设最左边的L型文本索引已经是
// 插入sa，按LMS子字符串后缀排序，并位于相应字符桶的
// 左端。
// 每个LMS子字符串的形式为（作为regexp）/S+L+S/：
// 一个或多个S型、一个或多个L型、最终S型。
// INDUCTSUB_8_32只在sa的右端按排序顺序为每个LMS子字符串留下最左边的S型文本
// 索引。
// 也就是说，它删除了条目中存在的L型索引，
// 并插入但随后删除了内部S型索引，
// 将LMS子字符串开始索引打包到sa[len（sa）-numLMS:]中。
// /（递归只处理LMS子字符串开始索引。）
func induceSubS_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶右侧的位置。
	bucketMax_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除下面bucket[cB]的边界检查

	// 类似于上面的induceSubL\u 8\u 32，
	// 当我们从右到左扫描数组时，每个sa[i]=j>0都是正确的
	// 排序后缀数组项（对于文本[j：]），我们知道j-1是S类型。
	// 因为j-1是S类型，现在将其插入sa将正确排序。
	// 但是我们想区分S型j-1和L型j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果j-1前面有类型L，我们通过对其求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证将
	// 发生在sa[i´处，对于某些i´<i，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次遍历可以看到索引j、j-1、j-2、j-3、
	// 等等，它们按排序但不一定是相邻的顺序，直到找到
	// 前面有一个L类型的索引，此时必须停止。
	// 该索引（前面有一个类型为L的索引）是LMS子字符串的开始。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 然后将sa[i]<0翻转为-sa[i]，并压缩到sa的顶部，
	// 这样循环结束时，sa的顶部正好包含
	// LMS子字符串开始索引，按LMS子字符串排序。

	// 缓存最近使用的bucket索引：
	cB := byte(0)
	b := bucket[cB]

	top := len(sa)
	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		sa[i] = 0
		if j < 0 {
			// 为调用者保留发现的LMS子字符串开始索引。
			top--
			sa[top] = int32(-j)
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是S型，
		// 所以我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，请将k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将-k排队以保存给调用者。
		k := j - 1
		c1 := text[k]
		c0 := text[k-1]
		if c0 > c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int32(k)
	}
}

// length_8_32计算并记录文本中每个LMS子字符串的长度。
// 索引j处的LMS子字符串的长度存储在sa[j/2]，
// 避免存储在sa上半部分的LMS子字符串索引。
// （如果索引j是LMS子字符串的开始，则索引j-1是L类型，不能使用。）
// 有两个例外，都是为下面的名称_8_32中的优化而做的。
// 
// 首先，最后的LMS子串被记录为长度为0，否则
// 不可能，而不是给它一个包含隐式哨兵的长度。
// 这确保了最终LMS子串的长度不等于所有其他子串
// 因此可以在不进行文本比较的情况下检测为不同
// （这是不平等的，因为它是唯一以隐式哨兵
// 结尾的，文本比较会有问题，因为隐式哨兵
// 实际上不存在于文本[len（text）]）。
// 
// 第二，为了完全避免文本比较，如果LMS子字符串非常短，
// sa[j/2]记录其实际文本而不是其长度，因此如果两个这样的
// 子字符串具有匹配的“长度”，则根本不需要读取文本。
// “极短”的定义是文本字节必须打包成uint32，
// 无符号编码e必须是≥ len（text），因此可以将其与有效长度区分开来。
func length_8_32(text []byte, sa []int32, numLMS int) {
	end := 0 // 当前LMS子串结束的索引（0表示最终的LMS子串）

	// 将N个文本字节编码为一个“长度”字
	// 每个字节加1，将它们打包到字的底部
	// N*8位，然后按位反转结果。
	// 也就是说，文本序列abc（十六进制41 42 43）
	// 编码为^uint32（0x42_43_44）。
	// LMS子字符串不能以0xFF开头或结尾。
	// 添加1确保编码的字节序列不会以0x00开始或结束，因此当前字节可以是
	// 区别于顶部位的零填充，
	// 因此长度不需要单独编码。
	// 反转字节会增加仍然使用
	// 4字节编码的可能性≥ len（文本）。
	// 特别是，如果第一个字节是ASCII（<=0x7E，所以+1<=0x7F）
	// 那么将设置反转的高位，
	// 使其明显不是有效长度（它将是负的）。
	// 
	// cx保存预反转编码（压缩递增字节）。ABCFDG＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊。

	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		cx = cx<<8 | uint32(c1+1) // 仅字节
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 索引j=i+1是LMS子字符串的开始。
			// 计算要存储在sa中的长度或编码文本[j/2]。
			j := i + 1
			var code int32
			if end == 0 {
				code = 0
			} else {
				code = int32(end - j)
				if code <= 32/8 && ^cx >= uint32(len(text)) { // 仅字节
					code = int32(^cx) // 仅字节
				} // 仅字节
			}
			sa[j>>1] = code
			end = j + 1
			cx = uint32(c1 + 1) // 仅字节
		}
	}
}

// 分配ID_8_32为
// 关于字符串顺序和相等性的LMS子字符串集分配密集的ID编号，
// 返回分配的最大ID。
// 例如，给定输入“abababababab”，LMS子串
// 是“aba”、“aba”和“ab”，重新编号为21。
// sa[len（sa）-numLMS:]保存LMS子字符串索引
// 按字符串顺序排序，因此要分配数字，我们可以
// 索引j处LMS子字符串的新ID被写入sa[j/2]，
// 覆盖之前存储在那里的长度（按上面的长度_8_32）。
func assignID_8_32(text []byte, sa []int32, numLMS int) int {
	id := 0
	lastLen := int32(-1) // 不可能的
	lastPos := int32(0)
	for _, j := range sa[len(sa)-numLMS:] {
		// 索引j处的LMS子字符串是新的，还是与我们上次看到的相同？
		n := sa[j/2]
		if n != lastLen {
			goto New
		}
		if uint32(n) >= uint32(len(text)) {
			// /“长度”实际上是全文编码的，它们匹配。
			goto Same
		}
		{
			// 比较实际文本。
			n := int(n)
			this := text[j:][:n]
			last := text[lastPos:][:n]
			for i := 0; i < n; i++ {
				if this[i] != last[i] {
					goto New
				}
			}
			goto Same
		}
	New:
		id++
		lastPos = j
		lastLen = n
	Same:
		sa[j/2] = int32(id)
	}
	return id
}

// map_32将文本中的LMS子字符串映射到它们的新ID，
// 为递归生成子问题。
// 映射本身主要由assignID_8_32应用：
// sa[i]要么是0，要么是索引2*i处LMS子字符串的ID，要么是索引2*i+1处LMS子字符串的ID。
// 要生成子问题，我们只需删除零
// 并将ID更改为ID-1（我们的ID从1开始，但文本字符从0开始）。
// 
// map_32将作为递归输入的结果
// 打包到sa的顶部，以便将递归结果存储在sa的底部，这为扩展_8_32做好了准备。
func map_32(sa []int32, numLMS int) {
	w := len(sa)
	for i := len(sa) / 2; i >= 0; i-- {
		j := sa[i]
		if j > 0 {
			w--
			sa[w] = j - 1
		}
	}
}

// recurse_32递归调用sais_32来解决我们构建的子问题。
// 子问题在sa的右端，后缀数组结果将是
// 写在sa的左端，sa的中间可用作
// 临时频率和存储桶。
func recurse_32(sa, oldTmp []int32, numLMS, maxID int) {
	dst, saTmp, text := sa[:numLMS], sa[numLMS:len(sa)-numLMS], sa[len(sa)-numLMS:]

	// 为递归调用设置临时空间。
	// 我们必须向sais_32传递一个tmp缓冲区，该缓冲区至少包含maxID条目。
	// 
	// 保证子问题的长度不超过len（sa）/2，
	// 以便sa可以同时容纳子问题及其后缀数组。
	// 然而，几乎所有的时候，子问题都有长度<len（sa）/3，
	// 在这种情况下，有一个子问题大小的sa中间，
	// 我们可以重用为临时空间（saTmp）。
	// 当从sais_8_32调用recurse_32时，oldTmp的长度为512 
	// （从text_32），saTmp通常会大得多，所以我们将使用saTmp。
	// 当更深的递归返回到递归时，现在oldTmp是
	// 从最顶层递归开始的saTmp，它通常比
	// 当前的saTmp大（因为当前sa随着递归的加深变得越来越小），我们一直在重复使用最顶级的
	// 大型saTmp，而不是提供的小型saTmp。
	// 
	// 为什么子问题的长度经常小于len（sa）/3？
	// 有关合理的解释，请参见农、张和陈，第3.6节。简而言之，len（sa）/2案例将对应于SLSL模式
	// 在输入中，大小输入字节的完美交替。
	// Real text不会这么做。如果每个L-type索引后面随机跟随着一个L-type或S-type索引，那么一半的子字符串将是SLS形式的，但另一半更长。在这一半中，
	// 一半（总共四分之一）将是SLL；八分之一是SLLL，以此类推。
	// 不计算每个中的最后一个S（与下一个中的第一个S重叠），
	// 计算出的平均长度为2×½+3×¼+4×2⅛ + ... = 3.
	// 我们需要的空间进一步减少了，因为许多像SLS这样的短模式通常会在整个文本中重复相同的字符序列，从而减少相对于numms的maxID。
	// 
	// 对于短输入，平均值可能不利于我们，但我们
	// 通常可以使用
	// 最顶端调用中可用的长度为512的tmp。（此外，短期拨款也不是什么大问题。）
	// 
	// 对于病理输入，我们退回到分配长度为
	// max（maxID，numls/2）的新tmp。这一级别的递归需要maxID，
	// 而所有更深层次的递归将需要不超过numms/2，
	// 因此这一分配保证足以满足整个堆栈
	// 的递归调用。
	tmp := oldTmp
	if len(tmp) < len(saTmp) {
		tmp = saTmp
	}
	if len(tmp) < numLMS {
		// TestSAIS/forcealloc到达此代码。
		n := maxID
		if n < numLMS/2 {
			n = numLMS / 2
		}
		tmp = make([]int32, n)
	}

	// sais_32要求调用者安排清除dst，
	// 因为通常调用者可能知道dst是
	// 新分配且已清除。但这个不是。
	for i := range dst {
		dst[i] = 0
	}
	sais_32(text, maxID, dst, tmp)
}

// unmap_8_32将子问题反映射回原始问题。
// sa[:numLMS]是LMS子串数，它不再重要。
// sa[len（sa）-numLMS:]是这些LMS子字符串编号的排序列表。
// 关键部分是，如果列表中显示K，则表示第K个子字符串。
// 我们可以用LMS子字符串的索引替换sa[：numls]。
// 那么如果列表上写的是K，那么它实际上意味着sa[K]。
// 将列表映射回LMS子字符串索引后，
// 我们可以将它们放入正确的存储桶中。
func unmap_8_32(text []byte, sa []int32, numLMS int) {
	unmap := sa[len(sa)-numLMS:]
	j := len(unmap)

	// /“LMS子串迭代器”（见上文placeLMS_8_32）。
	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 填充逆映射。
			j--
			unmap[j] = int32(i + 1)
		}
	}

	// 对子问题后缀数组应用逆映射。
	sa = sa[:numLMS]
	for i := 0; i < len(sa); i++ {
		sa[i] = unmap[sa[i]]
	}
}

// expand_8_32将压缩、排序的LMS后缀索引
// 从sa[：numms]分配到sa中相应桶的顶部，
// 保留排序顺序，并为L型索引
// 留出空间，以便通过诱导_8_32将其插入排序序列。
func expand_8_32(text []byte, freq, bucket, sa []int32, numLMS int) {
	bucketMax_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除对

	// 下面的bucket[c]的绑定检查，在sa中向后循环，始终跟踪
	// 从sa填充的下一个索引[：numms]。
	// 当我们找到一个时，填充它。
	// 将剩余插槽归零；他们有死的价值观。
	x := numLMS - 1
	saX := sa[x]
	c := text[saX]
	b := bucket[c] - 1
	bucket[c] = b

	for i := len(sa) - 1; i >= 0; i-- {
		if i != int(b) {
			sa[i] = 0
			continue
		}
		sa[i] = saX

		// 加载下一个要放下的条目（如果有）。
		if x > 0 {
			x--
			saX = sa[x] // TODO bounds check 
			c = text[saX]
			b = bucket[c] - 1
			bucket[c] = b
		}
	}
}

// INDUCTL_8_32将L型文本索引插入sa，
// 假设最左边的S型索引按排序顺序插入sa的右半桶中。
// 它将所有L型索引保留在sa中，但最左边的L型索引将被否定，以标记它们
// 以便通过诱导子8_32进行处理。
func induceL_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶左侧的位置。
	bucketMin_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除桶[cB]的边界检查

	// 此扫描类似于上面的InquiredSubl_8_32中的扫描。
	// 除最左边的L型索引外，其他所有索引都被清除。
	// 此扫描将保留所有L型索引和原始S型
	// 索引，但它将否定最左边的正L型索引
	// （导致_8_32的索引需要处理）。

	// expand_8_32省略了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket索引。
	cB := c1
	b := bucket[cB]
	sa[b] = int32(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j <= 0 {
			// 跳过空的或否定的条目（包括否定的零）。
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 所以我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，请将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则排队-k为调用者保存。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用者
		// 即可。调用方无法区分
		// 空插槽和非空零之间的区别，但无论如何也不需要
		// 来区分它们：最终的后缀数组将以
		// 结尾，在某个地方有一个零，这将是一个真正的零。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 < c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int32(k)
		b++
	}
}

func induceS_8_32(text []byte, sa, freq, bucket []int32) {
	// 初始化字符桶右侧的位置。
	bucketMax_8_32(text, freq, bucket)
	bucket = bucket[:256] // 消除桶[cB]在

	cB := byte(0)
	b := bucket[cB]

	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j >= 0 {
			// 下面的边界检查跳过未标记的条目。
			// /（此循环无法看到空条目；0表示实际的零索引。）
			continue
		}

		// 负j是一个工作队列条目；最后一个后缀数组重写为正j。
		j = -j
		sa[i] = int32(j)

		// 索引j在工作队列上（编码为-j，但现在已解码），
		// 意思是k:=j-1是L型，
		// 所以我们现在可以将k正确地放入sa。
		// 如果k-1是S-type，请将-k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（文本[k-1]>文本[k]），则将k排队以保存给调用者。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用者
		// 即可。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 <= c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int32(k)
	}
}
